package org.datastructure.firstday.sort;

import java.util.Arrays;

/**
 * 分成一个有序的队列和一个无序队列，第一个元素未有序，从第二哥元素开始
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        insertSort(arr);
        Arrays.stream(arr).forEach(e -> System.out.println(e));
    }

    public static void insertSort(int... arr) {

        // TODO: 无序数组从左往右与有序数组从右往左依次比较
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            // TODO: i=无序比较数下标，i-1是有序数组最右边第一个元素下标
            int insertIndex = i - 1;
            // TODO: 2021/7/5 如果当前有序数组元素小于当前无序元素，那么就将有序元素向右移动
            //  再用从右向左下一个有序元素与无序元素比较，如果还是小于有序元素，有序元素继续向右移动一位
            //  如果有序元素大于或等于无序元素，那么就将无序元素插入到有序数组的insertIndex+1位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {

                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //todo  否则跳出循环 表示不满足有序列表内元素大于当前无序元素或insertIndex<0）
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }
}
